import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/*
题目描述：二叉树的镜像
只要把非叶子结点的子结点交换位置即可
 */
public class E27_1 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode('a');
        root.left = new TreeNode('b');
        root.right = new TreeNode('c');
        root.left.left = new TreeNode('d');
        root.left.right = new TreeNode('e');

        root.right.left = new TreeNode('f');
        root.right.right = new TreeNode('g');

        PrintTree(root);

        Mirror(root);

        PrintTree(root);
    }

    public static void Mirror(TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            return;
        }
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        Mirror(root.left);
        Mirror(root.right);
    }

    public static void PrintTree(TreeNode root){
        if(root == null){
            return;
        }
        List<List<Character>> res =  helper(root);

        for(List<Character> a : res){
            for(Character b : a){
                System.out.print(b + "  ");
            }
            System.out.println();
        }
    }

    public static List<List<Character>> helper(TreeNode root){
        List<List<Character>> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            int len = queue.size();
            List<Character> list = new ArrayList<>();
            for(int i = 0; i < len; i++){
                TreeNode cur = queue.poll();
                list.add(cur.value);
                if(cur.left != null){
                    queue.add(cur.left);
                }
                if(cur.right != null){
                    queue.add(cur.right);
                }
            }
            res.add(list);
        }
        return res;
    }
}
/*
a
b  c
d  e  f  g
a
c  b
g  f  e  d
 */